package com.mccken.practice.top100.Top_1$20.Top_14;

import java.util.Arrays;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-02 21:40
 **/
public class ProductExceptSelf {

	// 这才是正常人的思维
	public int[] productExceptSelf(int[] nums) {
		int len = nums.length;
		int[] L = new int[len];
		int[] R = new int[len];

		int[] answer = new int[len];

		// L[i] 是索引为i坐车所有元素的乘积
		L[0] = 1;
		for (int i = 1; i < len; i++) {
			L[i] = nums[i - 1] * L[i - 1];
		}

		R[len - 1] = 1;
		for (int i = len - 1; i >= 0; i--) {
			R[i] = R[i + 1] * nums[i + 1];
		}

		for (int i = 0; i < len; i++) {
			answer[i] = L[i] * R[i];
		}
		return answer;

	}

	public int[] productExceptSelf1(int[] nums) {
		int n = nums.length;
		int[] ans = new int[n];
		Arrays.fill(ans, 1);

		int beforeSum = 1;
		int afterSum = 1;

		for (int i = 0, j = n - 1; i < n; i++, j--) {
			ans[i] *= beforeSum;
			ans[j] *= afterSum;

			beforeSum *= nums[i];
			afterSum *= nums[j];
		}

		return ans;

	}
}
